package cn.xiaolang.function.data_structure;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 迷路的机器人
 * <p>
 * 设想有个机器人坐在一个网格的左上角，网格r行c列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。
 * 设计一种算法，寻找机器人从左上角移动到右下角的路径。
 * <p>
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 * <p>
 * 返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。
 * <p>
 * 示例 1:
 * 输入:
 * [
 * [0,0,0],
 * [0,1,0],
 * [0,0,0]
 * ]
 * 输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
 * <p>
 * 解释:
 * 输入中标粗的位置即为输出表示的路径，即
 * 0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）
 * 说明：r和c的值均不超过100。
 */
public class No16pathWithObstacles {

    public static void main(String[] args) {
        int[][] obstacleGrid = new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        No16pathWithObstacles obstacles = new No16pathWithObstacles();
        System.out.println(obstacles.pathWithObstacles(obstacleGrid));

    }

    private int m;
    private int n;
    private int[][] grid;

    /**
     * @param row      某行
     * @param col      某列
     * @param visited  是否看过
     * @param pathList 路径内容
     * @return true/false
     */
    private boolean dfs(int row, int col, boolean[][] visited, List<List<Integer>> pathList) {
        // 超出二维数据范围；遇到1受阻；已经记录过；
        if (row >= m || col >= n || grid[row][col] == 1 || visited[row][col]) {
            return false;
        }

        pathList.add(Arrays.asList(row, col));
        if (row == m - 1 && col == n - 1) {
            return true;
        }

        visited[row][col] = true;

        if (dfs(row + 1, col, visited, pathList) || dfs(row, col + 1, visited, pathList)) {
            return true;
        }

        pathList.remove(pathList.size() - 1);
        return false;
    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了97.62%的用户.
     * 内存消耗：42.9 MB, 在所有 Java 提交中击败了5.10%的用户.
     */
    public List<List<Integer>> pathWithObstacles(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        List<List<Integer>> ansList = new ArrayList<>();
        dfs(0, 0, new boolean[m][n], ansList);
        return ansList;
    }

}
